/**
 * 
 */
package com.gwcloud.leetcode.hot100;

import java.util.Arrays;

/**
 * @ClassName   : Leetcode0322 
 * @author      : ganwei 
 * @date        : 2020年5月14日
 * @Description : Leetcode0322 零钱兑换
 */
public class Leetcode0322 {
	
	/**
	 * -解题思路，动态规划!!自顶向下,之前写的是自底向上
	 */
    public int coinChange(int[] coins, int amount) {
    	//int[] memo = new int[amount+1];
    	//Arrays.fill(memo, -2);
    	//return dp(coins, amount, memo);
    	return dp(coins, amount);
    }
    /**
     * -自顶向下，递归，个人感觉递归会慢,且资源消耗较多
     */
    public int dp(int[] coins, int amount, int[] memo) {
    	if(amount < 0) {
    		return -1;
    	}
    	if(amount == 0 ) {
    		return 0;
    	}
    	if(memo[amount] != -2) return memo[amount];
    	int res = Integer.MAX_VALUE;
    	for(int coin : coins) {
    		int subproblem = dp(coins, amount-coin,memo);
    		if(subproblem == -1) continue;
    		res = Math.min(res, 1+subproblem);
    		
    	}
    	memo[amount] = res != Integer.MAX_VALUE ? res : -1;
    	return memo[amount];
    }
    
    /**
     * -动态规划，迭代解法
     */
    public int dp(int[] coins, int amount) {
    	int[] res = new int[amount+1];
    	Arrays.fill(res, amount+1);
    	
    	res[0] = 0;
    	for(int i = 0; i < res.length; i++) {
    		for(int coin : coins) {
    			if(i-coin < 0) continue;
    			res[i] = Math.min(res[i], 1+res[i-coin]);
    		}
    	}
    	
    	return res[amount] == amount+1 ? -1 : res[amount];
    }
    /**
     * -主函数
     */
    public static void main(String[] args) {
    	Leetcode0322 l0322 = new Leetcode0322();
    	int[] coins = {2186,419,83,408};
    	System.out.println(l0322.coinChange(coins, 3));
    	System.out.println(Integer.MAX_VALUE+1);
    }
    
}
